A flash storage device usually contains a flash controller and at least one flash chip. One limitation of the flash chip is that, although it can be read or programmed a byte or a word at a time in a random access fashion, the data stored in the flash chip can be erased only a block at a time. If the data in a data block of the flash chip need to be updated or replaced by new replacement data, rather than directly delete the data from the data block, the chip controller will mark the data to be replaced as “stale” and program the new replacement data into the same data block. When the data block is fully programmed, a garbage collection operation may be performed to the data block. For example, during the garbage collection operation, the data in the data block that are marked as “stale” may be deleted and the other data that are not marked as “stale” may be copied to another data block. After the garbage collection operation, the data block is empty, ready to store new data. When a plurality of data blocks inside a flash chip are full, the chip controller may select the data block with the least valid data from the plurality of data blocks as a garbage block and perform the garbage collection operation on the data block that has been marked as the garbage block.